package _06_binaryTree;

// 二叉树操作类，声明特定对二叉树操作的静态方法
public class BinaryTrees {
    
    private static int i = 0;
    
    // 返回以广义表表示字符串genlist构造的二叉树
    public static BinaryTree<String> createByGenList(String genlist) {
        int i = 0;
        BinaryTree<String> tree = new BinaryTree<String>();
        tree.root = createNode(genlist);
        return tree;
    }

    /*
    
    A(B(D(^, G), ^), C(E, F(H, ^)))观察这个二叉树广义表，你会得到以下信息：
    '('左边的表头是括号内中原子的父结点，'('意味着需要为'('左边的结点创建左右结点，而')'则意味着')'左边括号内的子树创建完了
    ','意味着刚创建完左子树要创右子树了
    
     */
    // 以从i开始的广义表表示字符串创建一颗以genlist[i]为根的子树，返回子树的根结点
    // 递归算法先创建根节点，再创建左子树、右子树
    private static BinaryNode<String> createNode(String genlist) {
        // TODO Auto-generated method stub
        BinaryNode<String> p = null;
        if (i < genlist.length()) {
            int end = i;
            while (i < genlist.length() && "(,)".indexOf(genlist.charAt(end)) == -1) {
                end++;
            }
            String data = genlist.substring(i, end);
            i = end;
            if ("^".equals(data)) {
                return null;
            }
            p = new BinaryNode<String>(data);
            System.out.println(data);
            if (i < genlist.length() && genlist.charAt(i) == '(') {
                // 跳过'('
                i++;
                // 创建左子树，递归调用
                p.left = createNode(genlist);
                // 跳过','
                i++;
                // 创建右子树，递归调用
                p.right = createNode(genlist);
                // 跳过')'
                i++;
            }
        }
        return p;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String genlist = "AA(BB(D(^,G),^),C(E,F(H,^)))";
        BinaryTree<String> bitree = BinaryTrees.createByGenList(genlist);
        System.out.println(bitree.toGenListString());
    }

}
